﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithms
{
    /// <summary>
    /// 最长回文子串
    /// https://leetcode.com/problems/longest-palindromic-substring/description/
    /// </summary>
    public class LongestPalindromicSubstring
    {
        /// <summary>
        /// 遍历所有子串 求最长子串
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static string Action1(string s)
        {
            List<string> list = new List<string>();
            if (s.Length < 2)
            {
                return s;
            } 

            for(var i = 0; i < s.Length; i++)
            {
                for(var j = i + 1; j < s.Length; j++)
                {
                   if(IsPalindromic3( s.Substring(i, j - i + 1)))
                    {
                        list.Add(s.Substring(i, j - i + 1));
                    }
                }
            }
            if (list.Any())
            {
                return list.OrderByDescending(x => x.Length).FirstOrDefault() ?? "";
            }

            return s[0].ToString(); 
        }
        /// <summary>
        /// 从字符串最大长度开始遍历
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static string Action2(string s)
        {
            if (s.Length < 2)
            {
                return s;
            }

            int length = s.Length;
            //获取s的指定长度子串,并判断是否回文
            for(int len = length; len > 0; len--)
            {
                for(int low=0;low< length - len+1; low++)
                {
                    var str = s.Substring(low, len);
                    if (IsPalindromic(str))
                    {
                        return str;
                    }
                }
            }

            return s[0].ToString();
            #region 参考代码
            //for (int size = s.Length; size > 0; size--)
            //{
            //    for (int low = 0, high = low + size - 1; high < s.Length; low++, high++)
            //    {
            //        var str = s.Substring(low, high - low + 1);
            //        if (IsPalindromic(str))
            //        {
            //            return str;
            //        }
            //    }
            //}
            #endregion

        }

        static int max = 0;
        static string result = "";

        /// <summary>
        /// 从中心字符开始寻找 向两边寻找最大
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static string Action3(string s)
        {
            max = 0;
            result = "";
            int len = s.Length;

            for (int i = 0; i < s.Length; i++)
            {
                explain(s, i, i + 1);
                explain(s, i, i);
            }



            return max > 0 ? result : s[0].ToString();
        }
        
        private static void explain(string s,int low,int hight)
        {
            int length = s.Length;
            int len = 0;
            while (low >= 0 && hight < length && s[low] == s[hight] )
            {
                len = hight - low + 1;

                if (len > max)
                {
                    result = s.Substring(low, len);
                    max = len;
                }
                low--;
                hight++;
            }
           
        }


        #region  知乎原文 from 
        public static String Action4(String s)
        {
            for (int size = s.Length; size > 0; size--)
            {
                for (int low = 0, high = low + size - 1; high < s.Length; low++, high++)
                {
                    if (shrinkCheckPalindrome(s, low, high))
                    {
                        return s.Substring(low, high -low+1);
                    }
                }
            }
            return s.Substring(0, 1);
        }
        public static bool shrinkCheckPalindrome(String s, int low, int high)
        {
            while (low <= high)
            {
                if (s[low] == s[high])
                {
                    low++; high--;
                }
                else
                {
                    return false;
                }
            }
            return true;
        }


        private static String res = "";
        public static String Action5(String s)
        {
            max = 0;
            res = "";
            if (s.Length == 1) { return s; }
            for (int i = 0; i < s.Length - 1; i++)
            {
                checkPalindromeExpand(s, i, i);
                checkPalindromeExpand(s, i, i + 1);
            }
            return res;
        }
        public static void checkPalindromeExpand(String s, int low, int high)
        {
            while (low >= 0 && high < s.Length)
            {
                if (s[low] == s[high])
                {
                    if (high - low + 1 > max)
                    {
                        max = high - low + 1;
                        res = s.Substring(low, high+1-low);
                    }
                    low--; high++;
                }
                else
                {
                    return;
                }
            }
        }
        #endregion


        #region 判断是否回文
        /// <summary>
        /// 判断是否回文(判断对应正序字符和反序字符是都相对)
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        private static bool IsPalindromic(string str)
        {
            int len = str.Length;
            if (len <= 1) return false;
            bool result = true;

            int loop = len / 2;
            for (var i = 0; i < loop; i++)
            {
                if (str[i] != str[len - 1 - i])
                {
                    result = false;
                    break;
                }

            }
            return result;
        }
        /// <summary>
        /// 判断回文 将字符串反转作比较 较慢
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        private static bool IsPalindromic2(string str)
        {
            var reStr = new string(str.ToArray().Reverse().ToArray());
            return reStr == str;
        }

        private static bool IsPalindromic3(string str)
        {
            var low = 0;
            var hight = str.Length - 1;
            while (low <= hight)
            {
                if (str[low] == str[hight])
                {
                    low++;
                    hight--;
                }
                else
                {
                    return false;
                }
            }
            return true;
        }
        #endregion



    }
    /// <summary>
    /// 获取最长公共子串
    /// </summary>
    public class LongestCommonSubstring
    {
        public static string LcsAction1(string s1,string s2)
        {
            if (s1.Last() == s2.Last())
            {

            }


            return "";
        }
    }



    
}
